package com.wtgroup.demo.leetcode.q236_二叉树的最近公共祖先;

import com.wtgroup.demo.common.util.TreeNode;
import com.wtgroup.demo.leetcode.org_bytedance.Q_二叉树的最近公共祖先;

import java.util.*;

/**
 * @see Q_二叉树的最近公共祖先
 * @author 60906
 * @date 2021/5/6 16:39
 */
public class Q236_Test {

    /**
     * 递归套路解
     * 8ms, 48%
     * [答案]
     * LC_A 递归方法就是本质就是这个, 但是那个理解起来费劲.
     */
    private class Solution_RecurseTemplate {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return func(root, p, q).ans;
        }

        private Info func(TreeNode x, TreeNode p, TreeNode q) {
            if (x==null) {
                return new Info(false, false, null);
            }

            Info leftInfo = func(x.left, p, q);
            Info rightInfo = func(x.right, p, q);
            boolean findP = x == p || leftInfo.findP || rightInfo.findP;
            boolean findQ = x == q || leftInfo.findQ || rightInfo.findQ;
            TreeNode ans = leftInfo.ans != null ? leftInfo.ans : rightInfo.ans;
            if (ans == null && findP && findQ) {
                ans = x;
            }

            return new Info(findP, findQ, ans);
        }

        class Info {
            boolean findP;
            boolean findQ;
            TreeNode ans;

            public Info(boolean findP, boolean findQ, TreeNode ans) {
                this.findP = findP;
                this.findQ = findQ;
                this.ans = ans;
            }
        }
    }

    /**
     * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/
     * 可以认为递归套路的信息极度压缩. 从而代码极度精简.
     * [精选]
     * 信息要求: 我只需要知道子树和我自己在内, 有没有 p 或 q . 有其一就可以了.
     * 没有, 返回 null .
     * 最后在 root 处:
     * (1) root 自己就是 p|q, root 一定就是所求了.
     * (2) 左右子树都有 p|q => 必一边一个, 那么 root 就是所求啦.
     * (3) 必定一侧子树有 p|q , 就是解, 透返即可.
     *
     */
    private class Solution_LC_B {

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || root == p || root == q) {
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            /*最坏判断 3 次
            if (left!=null && right!=null) {
                return root;
            }
            return left != null ? left : right;*/
            if(left == null) return right;
            if(right == null) return left;
            return root; // here, left, right !=null
        }

    }



    private class Solution_LC_B_RecurseTemplatePerf {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return func(root, p, q).PQ;
        }

        private Info func(TreeNode x, TreeNode p, TreeNode q) {
            if (x == null || x == p || x == q) {
                // null 时, 自然返回了null, 合并这里复用代码
                return new Info(x);
            }

            Info leftInfo = func(x.left, p, q);
            // 剪枝
            if (leftInfo.hasAns) {
                return leftInfo;
            }
            Info rightInfo = func(x.right, p, q);
            if (rightInfo.hasAns) {
                return rightInfo;
            }
            if (leftInfo.PQ != null && rightInfo.PQ != null) {
                // 必定一边一个 => 我就是解
                // return new Info(x, true);
                leftInfo.PQ = x; // 不 new 了
                leftInfo.hasAns = true;
                return leftInfo;
            }
            if (leftInfo.PQ != null) {
                return leftInfo;
            }
            if (rightInfo.PQ != null) {
                return rightInfo;
            }

            return new Info(null);
        }

        class Info {
            TreeNode PQ;
            boolean hasAns;

            public Info(TreeNode PQ) {
                this.PQ = PQ;
            }

            public Info(TreeNode PQ, boolean hasAns) {
                this.PQ = PQ;
                this.hasAns = hasAns;
            }
        }

    }

    /**
     * 9~14ms, 30%
     * 效率: 5分;
     * 简洁: 4分;
     */
    // 尝试回溯方式搞一下
    private class Solution_My_BackTrack {

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) {
                return null;
            }
            Deque<TreeNode> path = new LinkedList<>(); // ! ArrayDeque 不让放null !
            List<TreeNode> pParents = new ArrayList<>();
            List<TreeNode> qParents = new ArrayList<>();
            path.addLast(root);
            func(root, p, q, path, pParents, qParents);
            int len = Math.max(pParents.size(), qParents.size());
            for (int i = len - 1; i >= 0; --i) {
                TreeNode pp = i < pParents.size() ? pParents.get(i) : null;
                TreeNode qp = i < qParents.size() ? qParents.get(i) : null;
                if (pp==qp) {
                    return pp;
                }
            }

            return null;
        }

        private void func(TreeNode root, TreeNode p, TreeNode q, Deque<TreeNode> path, List<TreeNode> pParents, List<TreeNode> qParents) {
            if (root == null) {
                return;
            }
            // 剪枝
            if (!pParents.isEmpty() && !qParents.isEmpty()) {
                // p, q 的父路径都已经收集到了, 可以提前结束了
                return;
            }

            if (root == p) {
                pParents.addAll(path);
            }
            if (root == q) {
                qParents.addAll(path);
            }

            if (root.left != null) {
                path.addLast(root.left);
                func(root.left, p, q, path, pParents, qParents);
                path.removeLast();
            }
            if (root.right != null) {
                path.addLast(root.right);
                func(root.right, p, q, path, pParents, qParents);
                path.removeLast();
            }
        }


    }


}
